<?php
//冒泡排序
$array = array(9,8,7,5,6);

$count = count($array);

for($i=0; $i<$count; $i++){
    for($j=$count-1; $j>$i;$j--){
        if ($array[$j] < $array[$j-1])
        {
            $tmp = $array[$j];
            $array[$j] = $array[$j-1];
            $array[$j-1] = $tmp;
        }
    }
}
print_r($array);exit;

/*  $mem = new Memcache;
$mem->connect("10.7.15.144", 11211);
$te = $mem->set('key', 'This is a testds!', 0, 60);
var_dump($te);
$val = $mem->get('key');
echo $val; exit; */
header("Content-type: text/html; charset=utf-8");
function myHash($str) {
    // hash(i) = hash(i-1) * 33 + str[i]
    $hash = 0;
    $s    = md5($str);
    $seed = 5;
    $len  = 32;
    for ($i = 0; $i < $len; $i++) {
        // (hash << 5) + hash 相当于 hash * 33
        //$hash = sprintf("%u", $hash * 33) + ord($s{$i});
        //$hash = ($hash * 33 + ord($s{$i})) & 0x7FFFFFFF;
        $hash = ($hash << $seed) + $hash + ord($s{$i});
    }
     
    return $hash & 0x7FFFFFFF;
}

class ConsistentHash {
    // server列表
    public $_server_list = array();
    // 延迟排序，因为可能会执行多次addServer
    private $_layze_sorted = FALSE;
     
    public function addServer($server) {
        $hash = myHash($server);
        $this->_layze_sorted = FALSE;
         
        if (!isset($this->_server_list[$hash])) {
            $this->_server_list[$hash] = $server;
        }
         
        return $this;
    }
    
    public function removeServer($server)
    {
        $hash = myHash($server);
        $this->_layze_sorted = FALSE;
        
        if(isset($this->_server_list[$hash]))
        {
            unset($this->_server_list[$hash]);   
        }        
        return $this;        
    }
     
    public function find($key) {
        // 排序
        if (!$this->_layze_sorted) {
            ksort($this->_server_list);
            $this->_layze_sorted = TRUE;
        }
         
        $hash = myHash($key);
        $len  = sizeof($this->_server_list);
        if ($len == 0) {
            return FALSE;
        }
         
        $keys   = array_keys($this->_server_list);
        $values = array_values($this->_server_list);
        
        // 如果不在区间内，则返回最后一个server
        if ($hash <= $keys[0] || $hash >= $keys[$len - 1]) {
            return $values[$len - 1];
        }
         
        foreach ($keys as $key=>$pos) {
            $next_pos = NULL;
            if (isset($keys[$key + 1]))
            {
                $next_pos = $keys[$key + 1];
            }
             
            if (is_null($next_pos)) {
                return $values[$key];
            }
             
            // 区间判断
            if ($hash >= $pos && $hash <= $next_pos) {
                return $values[$key];
            }
        }
    }
}

/*
 * 假设 缓存服务器 ip 有 3台 
 * 192.168.33.10 
 * 192.168.33.11
 * 192.168.33.12*/

$consistentHash = new ConsistentHash();

/* $consistentHash
->addServer("10.7.15.143")
->addServer("10.7.15.144")
->addServer("10.7.15.143#1")
->addServer("10.7.15.143#2")
->addServer("10.7.15.143#3")
->addServer("10.7.15.144#1")
->addServer("10.7.15.144#2")
->addServer("10.7.15.144#3"); */

$consistentHash->addServer("10.7.15.143");
$consistentHash->addServer("10.7.15.144");
$consistentHash->addServer("10.7.15.143#1");
$consistentHash->addServer("10.7.15.143#2");
$consistentHash->addServer("10.7.15.143#3");
$consistentHash->addServer("10.7.15.144#1");
$consistentHash->addServer("10.7.15.144#2");
$consistentHash->addServer("10.7.15.144#3");

/* ksort($consistentHash->_server_list);
print_r($consistentHash->_server_list);  */

echo "key1 at " . $consistentHash->find("key1") . "<br />";
echo "key2 at " . $consistentHash->find("key2") . "<br />"; 
echo "key3 at " . $consistentHash->find("key3") . "<br />"; 
echo "key4 at " . $consistentHash->find("key4") . "<br />";
echo "key5 at " . $consistentHash->find("key5") . "<br />";
echo "key6 at " . $consistentHash->find("key6") . "<br />";
echo "key7 at " . $consistentHash->find("key7") . "<br />";
echo "key8 at " . $consistentHash->find("key8") . "<br />";
echo "key9 at " . $consistentHash->find("key9") . "<br />";
echo "key10 at " . $consistentHash->find("key10") . "<br />";
echo "key11 at " . $consistentHash->find("key11") . "<br />";
echo "key12 at " . $consistentHash->find("key12") . "<br />"; 
